The present invention relates to a method and system for decoding intersymbol interference (ISI) channels for digital communication. More specifically, this invention relates to the use of a complement states grouping technique (CSGT) for reducing the number of states of a Viterbi detector (VD) for ISI channels.
In decoding an ISI channel, maximum likelihood sequence estimation (MLSE), implemented with a well-known Viterbi detector, has a significant performance gain compared to other detection techniques, such as a decision-feedback equalizer. However, the implementation complexity of MLSE is generally larger than other detection techniques, and the increase in complexity could present a challenge for low-power and high-speed implementation. It is therefore desirable to reduce the implementation complexity of the Viterbi detector at the expense of a reasonable, preferably negligible, performance loss compared to MLSE.
It is well known that the complexity of the Viterbi detector is directly related to the number of states. The number of states is determined by:
MKxe2x80x83xe2x80x83equation (1) 
where M is the size of the channel input signal set and K is the length of the overall channel impulse response or the channel memory.
A classical technique for reducing the number of states of the Viterbi detector is described by M. V. Eyuboglu and S. U. H. Qureshi in an article entitled xe2x80x9cReduced-State Sequence Estimation with Set Partitioning and Decision Feedback,xe2x80x9d IEEE Transactions on Communications, Vol. 36, No. 1, pp. 13-20, January 1989, incorporated herein by reference. In the reduced-state sequence estimation (RSSE) technique described in the above-referenced article, each superstate in a reduced-state (RS) trellis is formed by combining states of an original maximum likelihood (ML) trellis using Ungerboeck-like set partitioning principles set forth in G. Ungerboeck, xe2x80x9cChannel Coding with Multilevel/Phase Signals,xe2x80x9d IEEE Transactions on Information Theory, Vol. IT-28, pp. 55-67, January 1982, incorporated herein by reference. In the case of binary transmission, this classical RSSE technique simply becomes a state-truncation technique, where each superstate in the RS trellis is formed by truncating the ML state vector to a suitable length Kxe2x80x2, wherein Kxe2x80x2 less than K.
Although the aforementioned technique provides a good tradeoff between complexity and performance for many communication channels, there are numerous applications where the classical RSSE technique does not provide a satisfactory solution that reduces the complexity with a reasonable performance loss. For example, for an Extended Partial Response, Class 4, (EPR4) channel with binary input, which is commonly encountered in magnetic recording systems, the loss caused by the classical RSSE is intolerable. Therefore, what is needed is a reduced state technique which ensures negligible performance loss while reducing the complexity of the Viterbi detector.
The present invention, accordingly, provides a method and a system for implementing reduced state Viterbi detectors for ISI channels while ensuring a negligible performance loss. In one embodiment, the method includes the steps of determining state distances for all pairs of complement states and forming superstates of a reduced-state trellis by grouping pairs of complement states whose state distance satisfies a predetermined criterion. In another embodiment, the method for producing a reduced state trellis for the discrete system comprises the steps of determining a state distance for each pair of a plurality of pairs of complement states, forming a superstate from a pair of complement states of the plurality of pairs of complement states when the state distance of the pair satisfies a predetermined criterion, and keeping each state of a second pair of the plurality of pairs of complement states when the state distance of the second pair does not satisfy the predetermined criterion. In yet another embodiment, the method comprises steps of determining a state distance for a pair of complement states of the discrete channel, forming a superstate of a reduced-state trellis by grouping the pair of complement states if the state distance of the pair of complement states satisfies a predetermined criterion, and keeping each state of the pair of complement states if the state distance for the pair of complement states does not satisfy the predetermined criterion.
In one embodiment, the system comprises a channel encoder for encoding a data string to produce an encoded data string; a discrete time channel coupled to the channel encoder for transferring the encoded data string; a reduced-state detector coupled to the discrete time channel, which utilizes the complement states grouping technique (CSGT) to reduce the number of states in the detector and decodes the discrete time channel output sequence to generate the encoded data string; and a channel decoder coupled to the reduced-state detector for recovering the user data string from the encoded data string.
An advantage achieved with the present invention is that it reduces the number of states of the Viterbi detector, therefore, reducing its complexity. In most of the channels, the number of states can be reduced by a factor of about two.
Another advantage achieved with the present invention is that it ensures a negligible performance loss compared to MLSE, which is not achievable with the classical RSSE technique for channels such as the EPR4 channel.
Another advantage achieved with the present invention is that it generally causes no extra error propagation, which is a common problem for other reduced state techniques.